/*
 *
 *
 *
 *
 *
 *
 *要过年了，老板准备发年终奖，老板准备根据员工的平时表现对比发放奖金，最低发888，每档再增加1000块。
由于工作表现记录有点问题，可能存在矛盾的描述，所以，如果无法发放的话，则所有人，每人发888元。
老板把这个任务交给你，希望你帮他算出一共需要给多少奖金，每人需要发多少奖金？

输入
第一行是一个整数K，表示样例的个数。 每个样例的第一行是两个整数n(1≤n≤10000)和m(0≤m≤50000)，分别表示员工的人数以及工作表现记录的数目，员工的编号从1到n。
以后的m行为两个整数a和b(1≤a≠b≤n)，表示员工a的工作表现比b好。
输入数据保证工作表现不会有重复记录。

输出
每个样例先输出一行为奖金总数，然后再输出一行，按员工号的顺序，输出每个员工的奖金数，中间用一个空格隔开。
 *
 *
 */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 10010;
vector<int>G[MAXN];
int c[MAXN],  n, m, salary[MAXN];

int dfs(int u) {
    c[u] = -1;
    for(int v = 0; v < G[u].size(); v++) {
        int g = G[u][v];
        if(c[g] == -1) return -1;
        if(!c[g]) salary[g] = dfs(g);
        if(salary[g] == -1) return -1;
        if(salary[u] < salary[g]+1000) salary[u] = salary[g] + 1000;
    }
    c[u] = 1;
    return salary[u];
}

bool toposort() {
    memset(c, 0, sizeof(c));
    for(int u = 1; u <= n; u++)
        if(!c[u])
            if(dfs(u) == -1)
                return false;
    return true;
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d", &n, &m);
        for(int i = 0; i <= n ; i++) {
            salary[i] = 888;
            G[i].clear();
        }
        for(int i = 0; i < m; i++) {
            int u, v;
            scanf("%d %d",&u,&v);
            G[u].push_back(v);
        }
        if(toposort()) {
            int sum = 0;
            for(int i = 1; i <= n; i++) sum += salary[i];
            printf("%d\n", sum);
            for(int i = 1; i <= n; i++)
                printf("%d%c", salary[i], i == n ? '\n' : ' ');
        } else {
            printf("%d\n", n*888);
            while(n--) {
                printf("888");
                (!n) ? puts("") : putchar(' ');
            }
        }
    }
}
/*
 * 要过年了，老板准备发年终奖，老板准备根据员工的平时表现对比发放奖金，最低发888，每档再增加1000块。
由于工作表现记录有点问题，可能存在矛盾的描述，所以，如果无法发放的话，则所有人，每人发888元。
老板把这个任务交给你，希望你帮他算出一共需要给多少奖金，每人需要发多少奖金？

输入
第一行是一个整数K，表示样例的个数。 每个样例的第一行是两个整数n(1≤n≤10000)和m(0≤m≤50000)，分别表示员工的人数以及工作表现记录的数目，员工的编号从1到n。
以后的m行为两个整数a和b(1≤a≠b≤n)，表示员工a的工作表现比b好。
输入数据保证工作表现不会有重复记录。

输出
每个样例先输出一行为奖金总数，然后再输出一行，按员工号的顺序，输出每个员工的奖金数，中间用一个空格隔开。
 *
 *
 */